import java.util.ArrayList;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    //1.BM7数据流中的中位数
    ArrayList<Integer> val = new ArrayList<>();
    public void Insert(Integer num) {
        if (val.isEmpty())
            //val中没有数据，直接加入
            val.add(num);
            //val中有数据，需要插入排序
        else {
            int i = 0;
            //遍历找到插入点
            for (; i < val.size(); i++) {
                if (num <= val.get(i))
                    break;
            }
            //插入相应位置
            val.add(i, num);
        }
    }
    public Double GetMedian() {
        int n = val.size();
        if(n % 2 != 0) {
            return (double) val.get(n / 2);
        } else {
            double a = val.get(n / 2);
            double b = val.get(n / 2 - 1);
            return (a + b) / 2;
        }
    }
    //2.BM在二叉树中找到两节点的最近公共祖先
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return lowestCommonAncestorChild(root,o1,o2).val;
    }
    public TreeNode lowestCommonAncestorChild(TreeNode root ,int o1, int o2) {
        if(root == null) {
            return null;
        }
        if(root.val == o1 || root.val == o2) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestorChild(root.left,o1,o2);
        TreeNode rightTree = lowestCommonAncestorChild(root.right,o1,o2);

        if(leftTree != null && rightTree != null) {
            return root;
        }
        else if(leftTree != null) {
            return leftTree;
        } else {
            return rightTree;
        }
    }
}
    public static void main(String[] args) {
        Main main = new Main();
        main.Insert(1);
        main.Insert(2);
        main.Insert(5);
        main.Insert(4);
        main.Insert(3);
    }
}